package com.frx.leetoffer.link;

import com.frx.chapterfive.ListNode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created with IDEA
 * @description  链表逆序
 * @author: xrf
 * @Date: 2019/5/8
 * @Time: 9:56
 */
public class ReverseLink {

    public static void main(String[] args){

        ListNode listNode = new ListNode(1,null);
        ListNode listNode1 = new ListNode(2,listNode);
        ListNode listNode2 = new ListNode(3,listNode1);
        ListNode listNode3 = new ListNode(4,listNode2);
        ListNode listNode4 = new ListNode(5,listNode3);
        //ArrayList list = printFromTailToHead(listNode3);
        //ArrayList<Integer> list = printTailToHead(listNode3);
        //ArrayList<Integer> list = printTailToHead(listNode4);
        ListNode head = listNode4;
        while (head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
        ListNode node = reverseTest(listNode4);
        ListNode head2 = node;
        while (head2 != null){
            System.out.print(head2.val + " ");
            head2 = head2.next;
        }
        System.out.println();
/*        ArrayList<Integer> list = printTailHead(listNode4);
        System.out.println(list);*/
    }

    /**
     * @description 借用栈来逆序打印
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printFromTailToHead(ListNode listNode){
        ArrayList<Integer> arrayList = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while (listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        while (!stack.empty()){
            arrayList.add(stack.pop());
        }
        return arrayList;
    }

    /**
     * @description 递归调用
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printTailToHead(ListNode listNode){
        ArrayList<Integer> list = new ArrayList<>();

        if (listNode != null){
            list.addAll(printTailToHead(listNode.next));
            list.add(listNode.val);
        }

        return list;
    }

    /**
     * @description 头插法  建一个虚拟头节点
     * @param listNode
     * @return
     */
    public static ArrayList<Integer> printTailHead(ListNode listNode){
        ArrayList<Integer> ret = new ArrayList<>();
        ListNode head = new ListNode(-1,null);
        while (listNode != null){
            ListNode node = listNode.next;
            listNode.next = head.next;
            head.next = listNode;
            listNode = node;
        }
        head = head.next;
        while (head != null){
            ret.add(head.val);
            head = head.next;
        }

        return ret;
    }
    public static ListNode reverseTest(ListNode listNode){
        if (listNode == null || listNode.next == null ){
            return listNode;
        }
        ListNode p1 = listNode;
        ListNode p2 = listNode.next;
        ListNode p3 = null;
        while (p2 != null){
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        listNode.next = null;
        listNode = p1;
        return listNode;
    }


    private static class ListNode{
        int val;
        ListNode next;

        ListNode(int val,ListNode next){
            this.val = val;
            this.next = next;
        }
    }

}
